{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "KNN.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": []
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.6.2"
    },
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kkAcociwf9Y3",
        "colab_type": "text"
      },
      "source": [
        "#  第3章 k近邻法"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tfyS6ufGf9Y5",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import numpy as np\n",
        "import pandas as pd\n",
        "import matplotlib.pyplot as plt\n",
        "import pprint\n",
        "\n",
        "from sklearn.datasets import load_iris\n",
        "from sklearn.model_selection import train_test_split\n",
        "\n",
        "from collections import Counter\n",
        "%matplotlib inline"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pO7DjPbxOWfV",
        "colab_type": "text"
      },
      "source": [
        "## KNN"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "A4m_-DcEf9Y4",
        "colab_type": "text"
      },
      "source": [
        "#### 距离度量"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "foi6L24Qf9Y8",
        "colab_type": "text"
      },
      "source": [
        "**distance**:  \n",
        "$ L_{p}\\left(x_{i}, x_{j}\\right)=\\left(\\sum_{l=1}^{n}\\left|x_{i}^{(l)}-x_{j}^{(l)}\\right|^{p}\\right)^{\\frac{1}{p}}$"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WNLAMMfDf9Y8",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def distance(x, y, p=2):\n",
        "    \"\"\"calculate type of P distance between two points.\n",
        "    input:\n",
        "        x: N*M shape array.\n",
        "        y: 1*M shape array.\n",
        "        p: type of distance\n",
        "        \n",
        "    output:\n",
        "        N*1 shape of distance between x and y.\n",
        "    \"\"\"\n",
        "    try:\n",
        "        dis = np.power(np.sum(np.power(np.abs((x - y)), p), 1), 1/p)\n",
        "    except:\n",
        "        dis = np.power(np.sum(np.power(np.abs((x - y)), p)), 1/p)\n",
        "    \n",
        "    return dis"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AkRiIfTQf9ZI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# load toy data\n",
        "iris = load_iris()\n",
        "df = pd.DataFrame(iris.data, columns=iris.feature_names)\n",
        "df['label'] = iris.target\n",
        "df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DnrG4bOCf9ZK",
        "colab_type": "code",
        "outputId": "d4590079-5b25-4fce-a726-db6cc25788fb",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 197
        }
      },
      "source": [
        "df.head()"
      ],
      "execution_count": 64,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": [
              "<div>\n",
              "<style scoped>\n",
              "    .dataframe tbody tr th:only-of-type {\n",
              "        vertical-align: middle;\n",
              "    }\n",
              "\n",
              "    .dataframe tbody tr th {\n",
              "        vertical-align: top;\n",
              "    }\n",
              "\n",
              "    .dataframe thead th {\n",
              "        text-align: right;\n",
              "    }\n",
              "</style>\n",
              "<table border=\"1\" class=\"dataframe\">\n",
              "  <thead>\n",
              "    <tr style=\"text-align: right;\">\n",
              "      <th></th>\n",
              "      <th>sepal length</th>\n",
              "      <th>sepal width</th>\n",
              "      <th>petal length</th>\n",
              "      <th>petal width</th>\n",
              "      <th>label</th>\n",
              "    </tr>\n",
              "  </thead>\n",
              "  <tbody>\n",
              "    <tr>\n",
              "      <th>0</th>\n",
              "      <td>5.1</td>\n",
              "      <td>3.5</td>\n",
              "      <td>1.4</td>\n",
              "      <td>0.2</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>1</th>\n",
              "      <td>4.9</td>\n",
              "      <td>3.0</td>\n",
              "      <td>1.4</td>\n",
              "      <td>0.2</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>2</th>\n",
              "      <td>4.7</td>\n",
              "      <td>3.2</td>\n",
              "      <td>1.3</td>\n",
              "      <td>0.2</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>3</th>\n",
              "      <td>4.6</td>\n",
              "      <td>3.1</td>\n",
              "      <td>1.5</td>\n",
              "      <td>0.2</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "    <tr>\n",
              "      <th>4</th>\n",
              "      <td>5.0</td>\n",
              "      <td>3.6</td>\n",
              "      <td>1.4</td>\n",
              "      <td>0.2</td>\n",
              "      <td>0</td>\n",
              "    </tr>\n",
              "  </tbody>\n",
              "</table>\n",
              "</div>"
            ],
            "text/plain": [
              "   sepal length  sepal width  petal length  petal width  label\n",
              "0           5.1          3.5           1.4          0.2      0\n",
              "1           4.9          3.0           1.4          0.2      0\n",
              "2           4.7          3.2           1.3          0.2      0\n",
              "3           4.6          3.1           1.5          0.2      0\n",
              "4           5.0          3.6           1.4          0.2      0"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 64
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2OtLSARVf9ZN",
        "colab_type": "code",
        "outputId": "8734156a-9184-433d-b93d-3e4843332df4",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 300
        }
      },
      "source": [
        "# plot dataset\n",
        "\n",
        "plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')\n",
        "plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')\n",
        "plt.xlabel('sepal length')\n",
        "plt.ylabel('sepal width')\n",
        "plt.legend()"
      ],
      "execution_count": 65,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<matplotlib.legend.Legend at 0x7fc13704e7f0>"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 65
        },
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAEKCAYAAAD9xUlFAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4zLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvnQurowAAH+pJREFUeJzt3X+UHWWd5/H3x6Y1PcOPrBAdSAeD\n4uQIAQlEkImjIjpoyIQsKMJRZyKszLooehzxiOMoRkfQjD+HszoIjihuMDIYAQWWBfE3YIdAgsH4\nEydp2SWGSQANENrv/lHVN522f9zqvs+9VXU/r3P6dFfdutXfpy70N1XP830eRQRmZmYAT+l0AGZm\nVh5OCmZm1uCkYGZmDU4KZmbW4KRgZmYNTgpmZtbgpGBmZg1OCmZm1uCkYGZmDXul/gWSeoABYDAi\nlox6bTmwEhjMd10SEZdNdL4DDjgg5s6dmyBSM7P6Wrt27W8jYtZkxyVPCsDbgPuAfcd5/SsR8ZZm\nTzZ37lwGBgZaEpiZWbeQ9Otmjkv6+EhSP3AyMOG//s3MrBxS9yl8EngX8IcJjjlN0npJV0uaM9YB\nks6RNCBpYOvWrUkCNTOzhElB0hLgwYhYO8Fh1wFzI+JI4GbgirEOiohLI2JhRCycNWvSR2JmZjZF\nKfsUFgFLJS0GZgD7SroyIl4/fEBEbBtx/GXARxPGY2Y2Lbt27WLLli089thjnQ5lXDNmzKC/v5/e\n3t4pvT9ZUoiIC4ALACS9FHjnyISQ7z8wIh7IN5eSdUibmZXSli1b2GeffZg7dy6SOh3OH4kItm3b\nxpYtWzjkkEOmdI621ylIWiFpab55nqQfS7oHOA9Y3u54zMya9dhjj7H//vuXMiEASGL//fef1p1M\nO4akEhG3AbflP79vxP7G3YRZ3axZN8jKmzbxm+07OWhmH+efNI9lC2Z3OiybprImhGHTja8tScGs\n26xZN8gF12xg564hAAa37+SCazYAODFYqXmaC7MEVt60qZEQhu3cNcTKmzZ1KCKrixtvvJF58+Zx\n6KGHcvHFF7f8/E4KZgn8ZvvOQvvNmjE0NMS5557LDTfcwMaNG1m1ahUbN25s6e/w4yOzBA6a2cfg\nGAngoJl9HYjGOqXV/Up33nknhx56KM9+9rMBOOOMM/j617/OYYcd1qqQfadglsL5J82jr7dnj319\nvT2cf9K8DkVk7TbcrzS4fSfB7n6lNesGJ33veAYHB5kzZ/fED/39/QwOTv18Y3FSMEtg2YLZXHTq\nEcye2YeA2TP7uOjUI9zJ3EWq2q/kx0dmiSxbMNtJoIul6FeaPXs2mzdvbmxv2bKF2bNb+9+Y7xTM\nzBIYr/9oOv1KL3jBC/jZz37Gr371K5544gmuuuoqli5dOvkbC3BSMDNLIEW/0l577cUll1zCSSed\nxPOe9zxOP/10Dj/88OmGuufvaOnZzMwM2F2k2Oqq9sWLF7N48eJWhDgmJwUzs0Sq2K/kx0dmZtbg\npGBmZg1OCmZm1uCkYGZmDU4KZmbW4KRgXW/NukEWXXwrh7z7Gyy6+NZpzU1jltpZZ53FM57xDObP\nn5/k/E4K1tVSTFpmltLy5cu58cYbk53fScG6WlUnLbOKWL8aPjEfLpyZfV+/etqnfPGLX8zTn/70\nFgQ3NhevWVfzYjiWzPrVcN15sCv/b2nH5mwb4MjTOxfXJHynYF0txaRlZgDcsmJ3Qhi2a2e2v8Sc\nFKyreTEcS2bHlmL7S8KPj6yrpZq0zIz9+rNHRmPtLzEnBet6VZy0zCrgxPft2acA0NuX7Z+GM888\nk9tuu43f/va39Pf384EPfICzzz57msHu5qRgHdPqRc3NSmW4M/mWFdkjo/36s4QwzU7mVatWtSC4\n8TkpWEcM1wcMDwcdrg8AnBisPo48vdQjjcbijmbrCNcHmJWTk4J1hOsDrKoiotMhTGi68TkpWEe4\nPsCqaMaMGWzbtq20iSEi2LZtGzNmzJjyOdynYB1x/knz9uhTANcHWPn19/ezZcsWtm7d2ulQxjVj\nxgz6+6c+7NVJwTrC9QFWRb29vRxyyCGdDiOp5ElBUg8wAAxGxJJRrz0N+CJwDLANeG1E3J86JisH\n1weYlU877hTeBtwH7DvGa2cD/xkRh0o6A/gI8No2xGRWKq7ZsLJI2tEsqR84GbhsnENOAa7If74a\nOFGSUsZkVjZe08HKJPXoo08C7wL+MM7rs4HNABHxJLAD2D9xTGal4poNK5NkSUHSEuDBiFjbgnOd\nI2lA0kCZe/3NpsI1G1YmKe8UFgFLJd0PXAW8TNKVo44ZBOYASNoL2I+sw3kPEXFpRCyMiIWzZs1K\nGLJZ+7lmw8okWVKIiAsioj8i5gJnALdGxOtHHXYt8Lf5z6/OjylnVYhZIl7Twcqk7XUKklYAAxFx\nLXA58CVJPwceIkseZl3FNRtWJqraP8wXLlwYAwMDnQ7DzKxSJK2NiIWTHeeKZqud967ZwKo7NjMU\nQY/EmcfN4UPLjuh0WGaV4KRgtfLeNRu48vb/aGwPRTS2nRjMJudZUq1WVt0xxpq4E+w3sz05KVit\nDI3TRzbefjPbk5OC1UrPOLOkjLffzPbkpGC1cuZxcwrtN7M9uaPZamW4M9mjj8ymxnUKZmZdwHUK\n1hGv+9wP+f4vHmpsL3rO0/nym47vYESd4zUSrIrcp2AtMzohAHz/Fw/xus/9sEMRdY7XSLCqclKw\nlhmdECbbX2deI8GqyknBLAGvkWBV5aRgloDXSLCqclKwlln0nKcX2l9nXiPBqspJwVrmy286/o8S\nQLeOPlq2YDYXnXoEs2f2IWD2zD4uOvUIjz6y0nOdgplZF3CdgnVEqrH5Rc7r+gCzqXNSsJYZHps/\nPBRzeGw+MK0/ykXOmyoGs27hPgVrmVRj84uc1/UBZtPjpGAtk2psfpHzuj7AbHqcFKxlUo3NL3Je\n1weYTY+TgrVMqrH5Rc7r+gCz6XFHs7XMcEduq0f+FDlvqhjMuoXrFMzMuoDrFEqqDGPoi8ZQhpjN\nrD2cFNqoDGPoi8ZQhpjNrH3c0dxGZRhDXzSGMsRsZu3jpNBGZRhDXzSGMsRsZu3jpNBGZRhDXzSG\nMsRsZu3jpNBGZRhDXzSGMsRsZu3jjuY2KsMY+qIxlCFmM2ufZHUKkmYA3wGeRpZ8ro6I9486Zjmw\nEhjMd10SEZdNdF7XKZiZFVeGOoXHgZdFxKOSeoHvSbohIm4fddxXIuItCeOwaXrvmg2sumMzQxH0\nSJx53Bw+tOyIaR9blvqHssRhVgaTJgVJTwNOA+aOPD4iVkz0vshuQR7NN3vzr2qVTxvvXbOBK2//\nj8b2UERje/Qf+yLHlqX+oSxxmJVFMx3NXwdOAZ4Efjfia1KSeiTdDTwI3BwRd4xx2GmS1ku6WtKc\nJuO2Nll1x+am9xc5tiz1D2WJw6wsmnl81B8Rr5zKySNiCDhK0kzga5LmR8S9Iw65DlgVEY9L+jvg\nCuBlo88j6RzgHICDDz54KqHYFA2N0+c01v4ix5al/qEscZiVRTN3Cj+QNPZD4SZFxHbgW8ArR+3f\nFhGP55uXAceM8/5LI2JhRCycNWvWdEKxgnqkpvcXObYs9Q9licOsLMZNCpI2SFoPvAi4S9Km/DHP\n8P4JSZqV3yEgqQ94BfCTUcccOGJzKXDfVBph6Zx53NhP9MbaX+TYstQ/lCUOs7KY6PHRkmme+0Dg\nCkk9ZMlndURcL2kFMBAR1wLnSVpK1l/xELB8mr/TWmy4g7iZEUVFji1L/UNZ4jAri0nrFCR9KSLe\nMNm+dnGdgplZca2sUzh81Il7GOfZv00u1Zj4IvUBKc9dpH1VvBaVs3413LICdmyB/frhxPfBkad3\nOiorsXGTgqQLgPcAfZIeHt4NPAFc2obYaifVmPgi9QEpz12kfVW8FpWzfjVcdx7sykdS7dicbYMT\ng41r3I7miLgoIvYBVkbEvvnXPhGxf0Rc0MYYayPVmPgi9QEpz12kfVW8FpVzy4rdCWHYrp3ZfrNx\nTHSncHT+41dH/NwQEXcli6qmUo2JL1IfkPLcRdpXxWtROTu2FNtvxsR9Ch/Lv88AFgL3kD0+OhIY\nAI5PG1r9HDSzj8Ex/uhNd0x8jzTmH73x6gZSnbtI+6p4LSpnv/7skdFY+83GMdHjoxMi4gTgAeDo\nvHjsGGABu2c1tQJSjYkvUh+Q8txF2lfFa1E5J74Pekcl2d6+bL/ZOJoZfTQvIjYMb0TEvZKelzCm\n2ko1Jr5IfUDKcxdpXxWvReUMdyZ79JEV0EydwiqyCfCuzHe9Dtg7Is5MHNuYXKdgZlZcK+sU3gi8\nGXhbvv0d4DPTiM0qpgy1B1ZxrpeojEmTQkQ8Bnwi/7IuU4baA6s410tUykQT4q3Ov2/IJ8Lb46t9\nIVonlaH2wCrO9RKVMtGdwvDjoulOjGcVVobaA6s410tUykRDUh/If3w58NSI+PXIr/aEZ51WZL0B\nr01gYxqvLsL1EqXUzCI7BwP/KumXkr4q6a2SjkodmJVDGWoPrOJcL1EpzXQ0vx8aC+W8CTgf+CTQ\nM9H7rB7KUHtgFed6iUpppk7hvcAiYG9gHfA94LsjHi+1lesUzMyKa2WdwqlkK6N9A/g28MMR6yrX\nVqrx9kXOW5Z1AVx7UDJ1H/Nf9/YV0YFr0czjo6Ml7Ut2t/AK4FJJD0bEi5JG1kGpxtsXOW9Z1gVw\n7UHJ1H3Mf93bV0SHrsWkHc2S5pNNbfG3wGvJJsO7NVlEJZBqvH2R85ZlXQDXHpRM3cf81719RXTo\nWjTz+OhisqktPg38KCJ2JY2oBFKNty9y3rKsC+Dag5Kp+5j/ureviA5di0nvFCJiSUR8NCJ+0A0J\nAdKNty9y3vHm/2/3ugCuPSiZuo/5r3v7iujQtWimTqHrpBpvX+S8ZVkXwLUHJVP3Mf91b18RHboW\nzTw+6jqpxtsXOW9Z1gVw7UHJ1H3Mf93bV0SHrsWkdQpl4zoFM7Pipl2nIOk6YNyMERFLpxhbV3P9\ng1lFXP8OWPsFiCFQDxyzHJZ8fPrnLXkdxkSPj/65bVF0Cdc/mFXE9e+Agct3b8fQ7u3pJIYK1GFM\nNEvqtyf6ameQdeH6B7OKWPuFYvubVYE6jEk7miU9F7gIOAyYMbw/Ip6dMK5acv2DWUXEULH9zapA\nHUYzQ1L/jWxN5ieBE4AvAlemDKquXP9gVhEaZxLo8fY3qwJ1GM0khb6IuIVspNKvI+JC4OS0YdWT\n6x/MKuKY5cX2N6sCdRjN1Ck8LukpwM8kvYVs7qO904ZVT65/MKuI4c7kVo8+qkAdRjPrKbwAuA+Y\nCXwQ2A/4aETcnj68P+Y6BTOz4lq2nkJE/Cg/4VOA8yLikSYDmEE2kd7T8t9z9fAqbiOOeRpZH8Ux\nwDbgtRFxfzPnL6pofUDV1hAoUntQ92uRdBx4kbHrqeJI2b6Sj6GflqJtq/O1mEAzo48WknU275Nv\n7wDOioi1k7z1ceBlEfGopF7ge5JuGHWHcTbwnxFxqKQzgI+QTc/dUkXrA6q2hkCR2oO6X4uk48CL\njF1PFUfK9lVgDP2UFW1bna/FJJrpaP488D8iYm5EzAXOJUsSE4rMo/lmb/41+lnVKcAV+c9XAydK\nrR8GU7Q+oGprCBSpPaj7tUg6DrzI2PVUcaRsXwXG0E9Z0bbV+VpMopmkMBQR3x3eiIjvkQ1PnZSk\nHkl3Aw8CN0fEHaMOmQ1szs/7JLAD2H+M85wjaUDSwNatW5v51XsoWh9QtTUEitQe1P1aJB0HXmTs\neqo4UravAmPop6xo2+p8LSbRTFL4tqR/lfRSSS+R9D+B2yQdLenoid4YEUMRcRTQDxybr+JWWERc\nGhELI2LhrFmzCr+/aH1A1dYQKFJ7UPdrkXQceJGx66niSNm+Coyhn7KibavztZhEM0nh+cCfA+8H\nLgSeBywAPkaT8yNFxHbgW8ArR700CMwBkLQX2cimbc2cs4ii9QFVW0OgSO1B3a9F0nHgRcaup4oj\nZfsqMIZ+yoq2rc7XYhLNjD46YSonljQL2BUR2yX1Aa8g60ge6VqytZ9/CLwauDUSzOVdtD6gamsI\nFKk9qPu1SDoOvMjY9VRxpGxfBcbQT1nRttX5WkyimTqFZwIfBg6KiFdJOgw4PiIun+R9R5J1IveQ\n3ZGsjogVklYAAxFxbT5s9Utkdx4PAWdExC8nOq/rFMzMimtZnQLwBbLRRv+Qb/8U+AowYVKIiPVk\nf+xH73/fiJ8fA17TRAxmZtYGzfQpHBARq4E/QGOU0DSnCiy/NesGWXTxrRzy7m+w6OJbWbNusNMh\nWRmsXw2fmA8Xzsy+r1/dmmNTKRpDGdpXtfPWTDN3Cr+TtD95jYGkF5INHa2tyhVsWXsUKWgqQ/FT\nyoKtqhXnleHzqIhm7hTeQdYh/BxJ3yebluKtSaPqsMoVbFl7FCloKkPxU8qCraoV55Xh86iIZkYf\n3SXpJcA8QMCmiNiVPLIOqlzBlrVHkYKmMhQ/pSzYqlpxXhk+j4qY9E5B0mvI1lT4MbAM+MpkRWtV\nV7mCLWuPIgVNZSh+SlmwVbXivDJ8HhXRzOOjf4yIRyS9CDiRbNTRZ9KG1VmVK9iy9ihS0FSG4qeU\nBVtVK84rw+dREU3NfZR/Pxn4XER8A3hqupA6b9mC2Vx06hHMntmHgNkz+7jo1CPcydztjjwd/vrT\nsN8cQNn3v/702B2VRY4tQ7xFj0/Vvqqdt4aaKV67nmw6ilcARwM7gTsj4vnpw/tjLl4zMyuulcVr\np5PNWfTP+ZQVBwLnTzdAs9orsiBPWVQt5rIshFOWOFqgmdFHvweuGbH9APBAyqDMKq/IgjxlUbWY\ny1J7UJY4WqSZPgUzK6rIgjxlUbWYy1J7UJY4WsRJwSyFIgvylEXVYi5L7UFZ4mgRJwWzFIosyFMW\nVYu5LLUHZYmjRZwUzFIosiBPWVQt5rLUHpQljhZxUjBLYcnHYeHZu/+VrZ5su4wdtsOqFnNZag/K\nEkeLTFqnUDauUzAzK66VdQpmaVRxbHeqmFPVB1TxGltHOSlYZ1RxbHeqmFPVB1TxGlvHuU/BOqOK\nY7tTxZyqPqCK19g6zknBOqOKY7tTxZyqPqCK19g6zknBOqOKY7tTxZyqPqCK19g6zknBOqOKY7tT\nxZyqPqCK19g6zknBOqOKY7tTxZyqPqCK19g6znUKZmZdoNk6Bd8pmK1fDZ+YDxfOzL6vX93+86aK\nwawg1ylYd0s1lr/IeV1PYCXiOwXrbqnG8hc5r+sJrEScFKy7pRrLX+S8riewEnFSsO6Waix/kfO6\nnsBKxEnBuluqsfxFzut6AisRJwXrbqnG8hc5r+sJrESS1SlImgN8EXgmEMClEfGpUce8FPg68Kt8\n1zURMWHvmusUzMyKK8N6Ck8Cfx8Rd0naB1gr6eaI2DjquO9GxJKEcVg7VXH+/iIxV7F9ZeDrVhnJ\nkkJEPAA8kP/8iKT7gNnA6KRgdVHF8fauJ0jP161S2tKnIGkusAC4Y4yXj5d0j6QbJB3ejngskSqO\nt3c9QXq+bpWSvKJZ0t7AvwNvj4iHR718F/CsiHhU0mJgDfDcMc5xDnAOwMEHH5w4YpuyKo63dz1B\ner5ulZL0TkFSL1lC+HJEXDP69Yh4OCIezX/+JtAr6YAxjrs0IhZGxMJZs2alDNmmo4rj7V1PkJ6v\nW6UkSwqSBFwO3BcRY84BLOnP8uOQdGwez7ZUMVliVRxv73qC9HzdKiXl46NFwBuADZLuzve9BzgY\nICI+C7waeLOkJ4GdwBlRtbm8bbfhTsMqjTIpEnMV21cGvm6V4vUUzMy6QBnqFKysPGZ8T9e/A9Z+\nAWIoW/XsmOXTX/XMrKKcFLqNx4zv6fp3wMDlu7djaPe2E4N1Ic991G08ZnxPa79QbL9ZzTkpdBuP\nGd9TDBXbb1ZzTgrdxmPG96SeYvvNas5Jodt4zPiejllebL9ZzTkpdBvP3b+nJR+HhWfvvjNQT7bt\nTmbrUq5TMDPrAq5TaKM16wZZedMmfrN9JwfN7OP8k+axbMHsTofVOnWva6h7+8rA17gynBSmac26\nQS64ZgM7d2WjVQa37+SCazYA1CMx1L2uoe7tKwNf40pxn8I0rbxpUyMhDNu5a4iVN23qUEQtVve6\nhrq3rwx8jSvFSWGafrN9Z6H9lVP3uoa6t68MfI0rxUlhmg6a2Vdof+XUva6h7u0rA1/jSnFSmKbz\nT5pHX++ehU59vT2cf9K8DkXUYnWva6h7+8rA17hS3NE8TcOdybUdfVT3ufDr3r4y8DWuFNcpmJl1\ngWbrFPz4yKzO1q+GT8yHC2dm39evrsa5rWP8+MisrlLWB7j2oLZ8p2BWVynrA1x7UFtOCmZ1lbI+\nwLUHteWkYFZXKesDXHtQW04KZnWVsj7AtQe15aRgVlcp187wuhy15ToFM7Mu4DoFMzMrzEnBzMwa\nnBTMzKzBScHMzBqcFMzMrMFJwczMGpwUzMyswUnBzMwakiUFSXMkfUvSRkk/lvS2MY6RpE9L+rmk\n9ZKOThWPTYPnzTfrGinXU3gS+PuIuEvSPsBaSTdHxMYRx7wKeG7+dRzwmfy7lYXnzTfrKsnuFCLi\ngYi4K//5EeA+YPTCxacAX4zM7cBMSQemismmwPPmm3WVtvQpSJoLLADuGPXSbGDziO0t/HHiQNI5\nkgYkDWzdujVVmDYWz5tv1lWSJwVJewP/Drw9Ih6eyjki4tKIWBgRC2fNmtXaAG1injffrKskTQqS\neskSwpcj4poxDhkE5ozY7s/3WVl43nyzrpJy9JGAy4H7IuLj4xx2LfA3+SikFwI7IuKBVDHZFHje\nfLOuknL00SLgDcAGSXfn+94DHAwQEZ8FvgksBn4O/B54Y8J4bKqOPN1JwKxLJEsKEfE9QJMcE8C5\nqWIwM7NiXNFsZmYNTgpmZtbgpGBmZg1OCmZm1uCkYGZmDU4KZmbW4KRgZmYNykoFqkPSVuDXnY5j\nHAcAv+10EAm5fdVV57aB29eMZ0XEpJPHVS4plJmkgYhY2Ok4UnH7qqvObQO3r5X8+MjMzBqcFMzM\nrMFJobUu7XQAibl91VXntoHb1zLuUzAzswbfKZiZWYOTwhRI6pG0TtL1Y7y2XNJWSXfnX/+tEzFO\nh6T7JW3I4x8Y43VJ+rSkn0taL+noTsQ5FU207aWSdoz4/Cq1xJykmZKulvQTSfdJOn7U65X97KCp\n9lX285M0b0Tcd0t6WNLbRx2T/PNLuchOnb0NuA/Yd5zXvxIRb2ljPCmcEBHjjYt+FfDc/Os44DP5\n96qYqG0A342IJW2LprU+BdwYEa+W9FTgT0a9XvXPbrL2QUU/v4jYBBwF2T88yZYm/tqow5J/fr5T\nKEhSP3AycFmnY+mgU4AvRuZ2YKakAzsdVLeTtB/wYrJlcImIJyJi+6jDKvvZNdm+ujgR+EVEjC7U\nTf75OSkU90ngXcAfJjjmtPzW7mpJc9oUVysF8L8lrZV0zhivzwY2j9jeku+rgsnaBnC8pHsk3SDp\n8HYGN02HAFuBf8sfb14m6U9HHVPlz66Z9kF1P7+RzgBWjbE/+efnpFCApCXAgxGxdoLDrgPmRsSR\nwM3AFW0JrrVeFBFHk92qnivpxZ0OqIUma9tdZNMBPB/4F2BNuwOchr2Ao4HPRMQC4HfAuzsbUks1\n074qf34A5I/FlgJf7cTvd1IoZhGwVNL9wFXAyyRdOfKAiNgWEY/nm5cBx7Q3xOmLiMH8+4NkzzSP\nHXXIIDDyDqg/31d6k7UtIh6OiEfzn78J9Eo6oO2BTs0WYEtE3JFvX032R3Skyn52NNG+in9+w14F\n3BUR/2+M15J/fk4KBUTEBRHRHxFzyW7vbo2I1488ZtTzvaVkHdKVIelPJe0z/DPwV8C9ow67Fvib\nfCTEC4EdEfFAm0MtrJm2SfozScp/Ppbs/5Ft7Y51KiLi/wKbJc3Ld50IbBx1WCU/O2iufVX+/EY4\nk7EfHUEbPj+PPmoBSSuAgYi4FjhP0lLgSeAhYHknY5uCZwJfy/+/2gv4XxFxo6T/DhARnwW+CSwG\nfg78Hnhjh2Itqpm2vRp4s6QngZ3AGVGtCs+3Al/OH0H8EnhjTT67YZO1r9KfX/6PlVcAfzdiX1s/\nP1c0m5lZgx8fmZlZg5OCmZk1OCmYmVmDk4KZmTU4KZiZWYOTgllB+UycY82QO+b+Fvy+ZZIOG7F9\nm6TarkdsneWkYFZ+y4DDJj3KrAWcFKx28srlb+STot0r6bX5/mMkfTufDO+m4erz/F/en8rnsL83\nr4RF0rGSfphPvvaDEZW0zcbweUl35u8/Jd+/XNI1km6U9DNJHx3xnrMl/TR/z+ckXSLpL8gq41fm\n8T0nP/w1+XE/lfSXLbp0Zq5otlp6JfCbiDgZsimXJfWSTZB2SkRszRPFPwFn5e/5k4g4Kp8g7/PA\nfOAnwF9GxJOSXg58GDityRj+gWwalLMkzQTulPR/8teOAhYAjwObJP0LMAT8I9lcPo8AtwL3RMQP\nJF0LXB8RV+ftAdgrIo6VtBh4P/DyqVwos9GcFKyONgAfk/QRsj+m35U0n+wP/c35H9UeYOScMasA\nIuI7kvbN/5DvA1wh6blkU273Fojhr8gmT3xnvj0DODj/+ZaI2AEgaSPwLOAA4NsR8VC+/6vAn09w\n/mvy72uBuQXiMpuQk4LVTkT8VNkyhYuBD0m6hWxG1B9HxPHjvW2M7Q8C34qI/yppLnBbgTAEnJav\nprV7p3Qc2R3CsCGm9v/h8Dmm+n6zMblPwWpH0kHA7yPiSmAl2SOZTcAs5Wv6SurVnguwDPc7vIhs\n5skdwH7snpZ4ecEwbgLeOmLGzgWTHP8j4CWS/oukvdjzMdUjZHctZsk5KVgdHUH2DP9usuftH4qI\nJ8hm0PyIpHuAu4G/GPGexyStAz4LnJ3v+yhwUb6/6L/GP0j2uGm9pB/n2+PK13n4MHAn8H3gfmBH\n/vJVwPl5h/Vzxj6DWWt4llTrepJuA94ZEQMdjmPviHg0v1P4GvD5iBi9cLtZUr5TMCuPC/O7m3uB\nX1HBpSSt+nynYGZmDb5TMDOzBicFMzNrcFIwM7MGJwUzM2twUjAzswYnBTMza/j/HUTN41iM/jsA\nAAAASUVORK5CYII=\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fJ4oYgrUf9ZQ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# X, y\n",
        "data = np.array(df.iloc[:100, [0, 1, -1]])\n",
        "X, y = data[:,:-1], data[:,-1]\n",
        "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fa9w8eBJf9ZS",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class KNN:\n",
        "    \"\"\"\n",
        "    KNN implementation of violence to calculate.\n",
        "    \"\"\"\n",
        "    def __init__(self, X_train, y_train, n_neighbors=1, p=2):\n",
        "        \"\"\"\n",
        "        n_neighbors: k\n",
        "                  p: type of distance\n",
        "        \"\"\"\n",
        "        self.k = n_neighbors\n",
        "        self.p = p\n",
        "        self.X_train = X_train\n",
        "        self.y_train = y_train\n",
        "    \n",
        "    def predict(self, X):\n",
        "        diss = distance(self.X_train, X, self.p)\n",
        "        diss_idx = np.argsort(diss) # return sorted index\n",
        "        top_k_idx = diss_idx[:self.k]\n",
        "        top_k_diss = diss[top_k_idx]\n",
        "        top_k_points = self.X_train[top_k_idx]\n",
        "        top_k_diss = diss[top_k_idx]\n",
        "        top_k_y = self.y_train[top_k_idx]\n",
        "        counter = Counter(top_k_y)\n",
        "        label = counter.most_common()[0][0]\n",
        "        return label, top_k_points, top_k_diss\n",
        "    \n",
        "    def score(self, X_test, y_test):\n",
        "        right_count = 0\n",
        "        for X, y in zip(X_test, y_test):\n",
        "            label = self.predict(X)[0]\n",
        "            if label == y:\n",
        "                right_count += 1\n",
        "        return right_count / len(X_test)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FGpKb23Ef9ZU",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "clf = KNN(X_train, y_train) "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "K3NqSBrBf9ZW",
        "colab_type": "code",
        "outputId": "717ef9ca-f21e-4258-89ed-13c146a3eda4",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "clf.score(X_test, y_test) # test on testset"
      ],
      "execution_count": 69,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1.0"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 69
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BkMKHgI8f9ZZ",
        "colab_type": "code",
        "outputId": "571b96f5-26cf-4597-c825-f17416a77240",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# test a single point \n",
        "\n",
        "test_point = [6, 2.7]\n",
        "clf.predict(test_point)"
      ],
      "execution_count": 95,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(1.0, array([[6. , 2.7]]), array([0.]))"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 95
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gHo2OpWPf9Zb",
        "colab_type": "code",
        "outputId": "4d698532-4c09-4874-a0bf-620bd65d67f0",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 300
        }
      },
      "source": [
        "plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')\n",
        "plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')\n",
        "plt.plot(test_point[0], test_point[1], 'bo', label='test_point')\n",
        "plt.xlabel('sepal length')\n",
        "plt.ylabel('sepal width')\n",
        "plt.legend()"
      ],
      "execution_count": 96,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "<matplotlib.legend.Legend at 0x7fc12d209940>"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 96
        },
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAEKCAYAAAD9xUlFAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4zLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvnQurowAAIABJREFUeJzt3X2YVXW5//H3zThHMBAUsWQGHB86\nXCogD+MDB80MPSiSGj6nFekv0p9laVGSHlCy0Kg080oPqWWKKHEIH1LUVNJSoeFBUNHU0mDw/CQU\nFEEDvH9/rDWbYZyHvWbvtfdaa39e1zXXzPrutb/c37Uv5p611vdeX3N3REREALqUOwAREUkOJQUR\nEclRUhARkRwlBRERyVFSEBGRHCUFERHJUVIQEZEcJQUREclRUhARkZyd4v4HzKwKaAAa3X1si9fG\nA9OBxrDpBne/ub3+9thjD6+rq4shUhGR7Fq8ePE/3b1PR/vFnhSAbwArgV3beP1ud/9avp3V1dXR\n0NBQlMBERCqFmb2ez36xXj4ys1rgBKDdv/5FRCQZ4r6ncB3wHeDDdvY5xcyWm9kcM+vX2g5mNsHM\nGsysYe3atbEEKiIiMSYFMxsLvOnui9vZ7T6gzt0HA48At7W2k7vPcPd6d6/v06fDS2IiItJJcd5T\nGAmcaGZjgK7ArmZ2h7uf07SDu69rtv/NwI9ijEdEEmjLli2sXr2a999/v9yhZELXrl2pra2lurq6\nU++PLSm4+yRgEoCZfRr4dvOEELbv5e5vhJsnEtyQFpEKsnr1anr06EFdXR1mVu5wUs3dWbduHatX\nr2afffbpVB8lr1Mws6lmdmK4eZGZPW9mzwIXAeNLHY+IlNf7779P7969lRCKwMzo3bt3QWddpZiS\nirsvABaEP09u1p47mxDJmnlLG5n+0EusWb+Zvr26MXH0AE4eWlPusBJJCaF4Cj2WJUkKIpVm3tJG\nJs1dweYt2wBoXL+ZSXNXACgxSKLpMRciMZj+0Eu5hNBk85ZtTH/opTJFJJIfJQWRGKxZvzlSu+Rv\n5kyoq4MuXYLvM2cW1t/69ev5xS9+0an3XnfddWzatKmwAFqYPHkyf/jDH9rdZ8GCBTz11FNF/Xeb\nKCmIxKBvr26R2iU/M2fChAnw+uvgHnyfMKGwxJC0pDB16lSOOeaYdvdRUhBJmYmjB9CtumqHtm7V\nVUwcPaBMEWXDZZdBy9/BmzYF7Z116aWX8uqrrzJkyBAmTpzI9OnTOeSQQxg8eDBTpkwB4L333uOE\nE07g4IMPZuDAgdx9991cf/31rFmzhqOPPpqjjz66zf67d+/OxRdfzEEHHcSoUaNoeirDsmXLOPzw\nwxk8eDCf+9znePvttwEYP348c+bMAYJnvU2ZMoVhw4YxaNAgXnzxRV577TVuuukmrr32WoYMGcKT\nTz7Z+cG3QklBJAYnD61h2rhB1PTqhgE1vboxbdwg3WQu0D/+Ea09H1dffTX77bcfy5Yt49hjj+Xl\nl19m0aJFLFu2jMWLF/PEE08wf/58+vbty7PPPstzzz3Hcccdx0UXXUTfvn15/PHHefzxx9vs/733\n3qO+vp7nn3+eo446iiuvvBKAL37xi1xzzTUsX76cQYMG5dpb2mOPPViyZAkXXHABP/7xj6mrq+P8\n88/n4osvZtmyZRx55JGdH3wrNPtIJCYnD61REiiy/v2DS0attRfDww8/zMMPP8zQoUMB2LhxIy+/\n/DJHHnkk3/rWt/jud7/L2LFjI/0i7tKlC2eccQYA55xzDuPGjWPDhg2sX7+eo446CoAvfelLnHba\naa2+f9y4cQAMHz6cuXPnFjK8vCgpiEhq/OAHwT2E5peQdtklaC8Gd2fSpEl89atf/chrS5Ys4YEH\nHuDyyy9n1KhRTJ48uZUeOha1jmDnnXcGoKqqiq1bt3bq34xCl49EJDXOPhtmzIC99waz4PuMGUF7\nZ/Xo0YN3330XgNGjR3PrrbeyceNGABobG3nzzTdZs2YNu+yyC+eccw4TJ05kyZIlH3lvWz788MPc\nPYI777yTI444gp49e7Lbbrvl7gfcfvvtubOGqDEXm84URCRVzj67sCTQUu/evRk5ciQDBw7k+OOP\n5/Of/zwjRowAgpvEd9xxB6+88goTJ06kS5cuVFdXc+ONNwIwYcIEjjvuuNy9hdZ87GMfY9GiRVx1\n1VXsueee3H333QDcdtttnH/++WzatIl9992XX/3qV3nH/NnPfpZTTz2Ve+65h5///OdFva9g7l60\nzkqhvr7etfKaSHasXLmSAw44oNxhxKZ79+65M49Sae2Ymtlid6/v6L26fCQiIjm6fCQiUgSHHXYY\nH3zwwQ5tt99+e8nPEgqlpCAiUgQLFy4sdwhFoctHIiKSo6QgIiI5unwkFU+L4YhspzMFqWhNi+E0\nrt+Ms30xnHlLG8sdmpTQ/PnzGTBgAPvvvz9XX311ucMpKyUFqWhaDEe2bdvGhRdeyIMPPsgLL7zA\nrFmzeOGFF8odVtno8pFUNC2Gkz7Fvty3aNEi9t9/f/bdd18AzjzzTO655x4OPPDAYoWcKjpTkIqm\nxXDSJY7LfY2NjfTr1y+3XVtbS2Nj5V4+VFKQiqbFcNJFl/vip8tHUtGaLjto9lE6xHG5r6amhlWr\nVuW2V69eTU1N5X7+SgpS8bQYTnr07dWNxlYSQCGX+w455BBefvll/v73v1NTU8Ndd93FnXfeWUiY\nqabLR1I285Y2MvLqx9jn0t8z8urHNA1UOhTH5b6ddtqJG264gdGjR3PAAQdw+umnc9BBBxUaamrp\nTEHKoumGYdP14aYbhoD+apc2xXW5b8yYMYwZM6YYIaaekoKURXs3DJUUpD263BcvXT6SslB9gEgy\nKSlIWag+QCSZlBSkLFQfIJJMuqcgZaH6AJFkij0pmFkV0AA0uvvYFq/tDPwGGA6sA85w99fijkmS\nQTcMRZKnFJePvgGsbOO184C33X1/4FrgmhLEI5I4qtkor3PPPZc999yTgQMHljuUsos1KZhZLXAC\ncHMbu5wE3Bb+PAcYZWYWZ0wiSaM1Hcpv/PjxzJ8/v9xhJELcZwrXAd8BPmzj9RpgFYC7bwU2AL1j\njkkkUfSQt4iWz4ZrB8IVvYLvy2cX3OWnPvUpdt999yIEl36xJQUzGwu86e6Li9DXBDNrMLOGtWvX\nFiE6keRQzUYEy2fDfRfBhlWAB9/vu6goiUECcZ4pjARONLPXgLuAz5jZHS32aQT6AZjZTkBPghvO\nO3D3Ge5e7+71ffr0iTFkkdJTzUYEj06FLS2S5ZbNQbsURWxJwd0nuXutu9cBZwKPufs5LXa7F/hS\n+POp4T4eV0wiSaSajQg2rI7WLpGVvE7BzKYCDe5+L3ALcLuZvQK8RZA8RCqKajYi6FkbXjpqpV2K\noiRJwd0XAAvCnyc3a38fOK0UMYgkmWo28jRqcnAPofklpOpuQXsBzjrrLBYsWMA///lPamtrufLK\nKznvvPMKDDadVNEsmXP5vBXMWriKbe5UmXHWYf246uRB5Q5LimHw6cH3R6cGl4x61gYJoam9k2bN\nmlWE4LJBSUEy5fJ5K7jjmX/ktre557aVGDJi8OkFJwFpmx6IJ5kya2Er15vbaReRHSkpSKZsa2Py\nWlvtkgyadFg8hR5LJQXJlKo2npLSVruUX9euXVm3bp0SQxG4O+vWraNr166d7kP3FCRTzjqs3w73\nFJq3SzLV1tayevVq9LSC4ujatSu1tZ2foqukIJnSdDNZs4/So7q6mn322afcYUjI0nbKVl9f7w0N\nDeUOQ0QkVcxssbvXd7SfzhSkqM7+5dP8+dW3ctsj99udmV8ZUcaIymfe0kZVKUvq6EazFE3LhADw\n51ff4uxfPl2miMpHayRIWikpSNG0TAgdtWeZ1kiQtFJSEImB1kiQtFJSEImB1kiQtFJSkKIZuV/r\nyxm21Z5lWiNB0kpJQYpm5ldGfCQBVOrso5OH1jBt3CBqenXDgJpe3Zg2bpBmH0niqU5BRKQCqE5B\nyiKuuflR+lV9gEjnKSlI0TTNzW+aitk0Nx8o6JdylH7jikGkUuieghRNXHPzo/Sr+gCRwigpSNHE\nNTc/Sr+qDxApjJKCFE1cc/Oj9Kv6AJHCKClI0cQ1Nz9Kv6oPECmMbjRL0TTdyC32zJ8o/cYVg0il\nUJ2CiEgFUJ1CQiVhDn3UGJIQs4iUhpJCCSVhDn3UGJIQs4iUjm40l1AS5tBHjSEJMYtI6SgplFAS\n5tBHjSEJMYtI6SgplFAS5tBHjSEJMYtI6SgplFAS5tBHjSEJMYtI6ehGcwklYQ591BiSELOIlE5s\ndQpm1hV4AtiZIPnMcfcpLfYZD0wHGsOmG9z95vb6VZ2CiEh0SahT+AD4jLtvNLNq4E9m9qC7P9Ni\nv7vd/WsxxiEFunzeCmYtXMU2d6rMOOuwflx18qCC901K/UNS4hBJgg6TgpntDJwC1DXf392ntvc+\nD05BNoab1eFXusqnhcvnreCOZ/6R297mnttu+cs+yr5JqX9IShwiSZHPjeZ7gJOArcB7zb46ZGZV\nZrYMeBN4xN0XtrLbKWa23MzmmFm/POOWEpm1cFXe7VH2TUr9Q1LiEEmKfC4f1br7cZ3p3N23AUPM\nrBfwOzMb6O7PNdvlPmCWu39gZl8FbgM+07IfM5sATADo379/Z0KRTtrWxj2n1tqj7JuU+oekxCGS\nFPmcKTxlZq1fFM6Tu68HHgeOa9G+zt0/CDdvBoa38f4Z7l7v7vV9+vQpJBSJqMos7/Yo+yal/iEp\ncYgkRZtJwcxWmNly4AhgiZm9FF7maWpvl5n1Cc8QMLNuwLHAiy322avZ5onAys4MQuJz1mGtX9Fr\nrT3Kvkmpf0hKHCJJ0d7lo7EF9r0XcJuZVREkn9nufr+ZTQUa3P1e4CIzO5HgfsVbwPgC/00psqYb\nxPnMKIqyb1LqH5ISh0hSdFinYGa3u/sXOmorFdUpiIhEV8w6hYNadFxFG9f+pWNxzYmPUh8QZ99R\nxpfGY5E6y2fDo1Nhw2roWQujJsPg08sdlSRYm0nBzCYB3wO6mdk7Tc3Av4AZJYgtc+KaEx+lPiDO\nvqOML43HInWWz4b7LoIt4UyqDauCbVBikDa1eaPZ3ae5ew9gurvvGn71cPfe7j6phDFmRlxz4qPU\nB8TZd5TxpfFYpM6jU7cnhCZbNgftIm1o70xhWPjjb5v9nOPuS2KLKqPimhMfpT4gzr6jjC+NxyJ1\nNqyO1i5C+/cUfhJ+7wrUA88SXD4aDDQAI+INLXv69upGYyu/9AqdE19l1uovvbbqBuLqO8r40ngs\nUqdnbXDJqLV2kTa0d/noaHc/GngDGBYWjw0HhrL9qaYSQVxz4qPUB8TZd5TxpfFYpM6oyVDdIslW\ndwvaRdqQz+yjAe6+omnD3Z8zswNijCmz4poTH6U+IM6+o4wvjccidZpuJmv2kUSQT53CLIIH4N0R\nNp0NdHf3s2KOrVWqUxARia6YdQpfBi4AvhFuPwHcWEBskjJJqD2QlFO9RGp0mBTc/X3g2vBLKkwS\nag8k5VQvkSrtPRBvdvh9RfggvB2+SheilFMSag8k5VQvkSrtnSk0XS4q9MF4kmJJqD2QlFO9RKq0\nNyX1jfDHY4B/c/fXm3+VJjwptyjrDWhtAmlVW3URqpdIpHwW2ekP/LeZ/c3MfmtmXzezIXEHJsmQ\nhNoDSTnVS6RKPjeap0BuoZyvABOB64Cq9t4n2ZCE2gNJOdVLpEo+dQqXAyOB7sBS4E/Ak80uL5WU\n6hRERKIrZp3COIKV0X4P/BF4utm6ypkV13z7KP0mZV0A1R4kTNbn/Gd9fFGU4Vjkc/lomJntSnC2\ncCwww8zedPcjYo2sjOKabx+l36SsC6Dag4TJ+pz/rI8vijIdiw5vNJvZQIJHW3wJOIPgYXiPxRZR\nAsQ13z5Kv0lZF0C1BwmT9Tn/WR9fFGU6FvlcPrqa4NEW1wN/cfctsUaUAHHNt4/Sb1LWBVDtQcJk\nfc5/1scXRZmORYdnCu4+1t1/5O5PVUJCgPjm20fpt63n/5d6XQDVHiRM1uf8Z318UZTpWORTp1Bx\n4ppvH6XfpKwLoNqDhMn6nP+sjy+KMh2LfC4fVZy45ttH6Tcp6wKo9iBhsj7nP+vji6JMx6LDOoWk\nUZ2CiEh0BdcpmNl9QJsZw91P7GRsFU31DyIpcf8lsPjX4NvAqmD4eBj708L7TXgdRnuXj35csigq\nhOofRFLi/kug4Zbt275t+3YhiSEFdRjtPSX1j+19lTLIrFD9g0hKLP51tPZ8paAOo8MbzWb2SWAa\ncCDQtand3feNMa5MUv2DSEr4tmjt+UpBHUY+U1J/RbAm81bgaOA3wB1xBpVVqn8QSQlr4yHQbbXn\nKwV1GPkkhW7u/ijBTKXX3f0K4IR4w8om1T+IpMTw8dHa85WCOox86hQ+MLMuwMtm9jWCZx91jzes\nbFL9g0hKNN1MLvbsoxTUYeSznsIhwEqgF/B9oCfwI3d/Jv7wPkp1CiIi0RVtPQV3/0vYYRfgInd/\nN88AuhI8SG/n8N+Z07SKW7N9dia4RzEcWAec4e6v5dN/VFHrA9K2hkCU2oOsH4tY54FHmbseVxxx\nji/hc+gLEnVsWT4W7chn9lE9wc3mHuH2BuBcd1/cwVs/AD7j7hvNrBr4k5k92OIM4zzgbXff38zO\nBK4heDx3UUWtD0jbGgJRag+yfixinQceZe56XHHEOb4UzKHvtKhjy/Kx6EA+N5pvBf6vu9e5ex1w\nIUGSaJcHNoab1eFXy2tVJwG3hT/PAUaZFX8aTNT6gLStIRCl9iDrxyLWeeBR5q7HFUec40vBHPpO\nizq2LB+LDuSTFLa5+5NNG+7+J4LpqR0ysyozWwa8CTzi7gtb7FIDrAr73QpsAHq30s8EM2sws4a1\na9fm80/vIGp9QNrWEIhSe5D1YxHrPPAoc9fjiiPO8aVgDn2nRR1blo9FB/JJCn80s/82s0+b2VFm\n9gtggZkNM7Nh7b3R3be5+xCgFjg0XMUtMnef4e717l7fp0+fyO+PWh+QtjUEotQeZP1YxDoPPMrc\n9bjiiHN8KZhD32lRx5blY9GBfJLCwcC/A1OAK4ADgKHAT8jz+Ujuvh54HDiuxUuNQD8AM9uJYGbT\nunz6jCJqfUDa1hCIUnuQ9WMR6zzwKHPX44ojzvGlYA59p0UdW5aPRQfymX10dGc6NrM+wBZ3X29m\n3YBjCW4kN3cvwdrPTwOnAo95DM/yjlofkLY1BKLUHmT9WMQ6DzzK3PW44ohzfCmYQ99pUceW5WPR\ngXzqFD4O/BDo6+7Hm9mBwAh3v6WD9w0muIlcRXBGMtvdp5rZVKDB3e8Np63eTnDm8RZwprv/rb1+\nVacgIhJd0eoUgF8TzDa6LNz+K3A30G5ScPflBL/sW7ZPbvbz+8BpecQgIiIlkM89hT3cfTbwIeRm\nCRX4qMDkm7e0kZFXP8Y+l/6ekVc/xryljeUOSZJg+Wy4diBc0Sv4vnx2cfaNS9QYkjC+tPWbMfmc\nKbxnZr0JawzM7HCCqaOZlbqCLSmNKAVNSSh+irNgK23FeUn4PFIinzOFSwhuCO9nZn8meCzF12ON\nqsxSV7AlpRGloCkJxU9xFmylrTgvCZ9HSuQz+2iJmR0FDAAMeMndt8QeWRmlrmBLSiNKQVMSip/i\nLNhKW3FeEj6PlOjwTMHMTiNYU+F54GTg7o6K1tIudQVbUhpRCpqSUPwUZ8FW2orzkvB5pEQ+l4/+\ny93fNbMjgFEEs45ujDes8kpdwZaURpSCpiQUP8VZsJW24rwkfB4pkdezj8LvJwC/dPffA/8WX0jl\nd/LQGqaNG0RNr24YUNOrG9PGDdJN5ko3+HT47PXQsx9gwffPXt/6jcoo+yYh3qj7xzW+tPWbQfkU\nr91P8DiKY4FhwGZgkbsfHH94H6XiNRGR6IpZvHY6wTOLfhw+smIvYGKhAYpkXpQFeZIibTEnZSGc\npMRRBPnMPtoEzG22/QbwRpxBiaRelAV5kiJtMSel9iApcRRJPvcURCSqKAvyJEXaYk5K7UFS4igS\nJQWROERZkCcp0hZzUmoPkhJHkSgpiMQhyoI8SZG2mJNSe5CUOIpESUEkDlEW5EmKtMWclNqDpMRR\nJEoKInEY+1OoP2/7X9lWFWwn8YZtk7TFnJTag6TEUSQd1ikkjeoURESiy7dOQWcKUj5pfL59XDHf\nfwlcuTtc0TP4fv8lRel25rSnqdt9DV3sQ+p2X8PMaU8XpV/JrnyK10SKL41zu+OKOab6gJnTnmbC\nlIPZtGUXAF5/uy8TpvQCnubsSSM6H69kms4UpDzSOLc7rphjqg+4bPreuYTQZNOWXbhs+t4F9SvZ\npqQg5ZHGud1xxRxTfcA/3v5EpHYRUFKQcknj3O64Yo6pPqD/bv8bqV0ElBSkXNI4tzuumGOqD/jB\nxNfZpXrTDm27VG/iBxNfL6hfyTYlBSmPNM7tjivmmOoDzp40ghlXPsveu63B+JC9d1vDjCuf1U1m\naZfqFEREKoDqFETyFVftQZR+01izIZmkOgWpbHHVHkTpN401G5JZOlOQyhZX7UGUftNYsyGZpaQg\nlS2u2oMo/aaxZkMyS0lBKltctQdR+k1jzYZklpKCVLa4ag+i9JvGmg3JLCUFqWxx1R5E6TeNNRuS\nWbHVKZhZP+A3wMcBB2a4+89a7PNp4B7g72HTXHdv9+6a6hRERKLLt04hzimpW4FvufsSM+sBLDaz\nR9z9hRb7PenuY2OMQ0pp+exg1syG1cE18VGTk/8Xb5SY0zi+JNBxS43YkoK7vwG8Ef78rpmtBGqA\nlklBsiKN8+1VTxA/HbdUKck9BTOrA4YCC1t5eYSZPWtmD5rZQaWIR2KSxvn2qieIn45bqsRe0Wxm\n3YH/Ab7p7u+0eHkJsLe7bzSzMcA84JOt9DEBmADQv3//mCOWTkvjfHvVE8RPxy1VYj1TMLNqgoQw\n093ntnzd3d9x943hzw8A1Wa2Ryv7zXD3enev79OnT5whSyHSON9e9QTx03FLldiSgpkZcAuw0t1b\nfQawmX0i3A8zOzSMZ11cMUnM0jjfXvUE8dNxS5U4Lx+NBL4ArDCzZWHb94D+AO5+E3AqcIGZbQU2\nA2d62p7lLds13TRM0yyTKDGncXxJoOOWKlpPQUSkAiShTkGSSnPGd3T/JbD41+DbglXPho8veNUz\nkbRSUqg0mjO+o/svgYZbtm/7tu3bSgxSgfTso0qjOeM7WvzraO0iGaekUGk0Z3xHvi1au0jGKSlU\nGs0Z35FVRWsXyTglhUqjOeM7Gj4+WrtIxikpVBo9u39HY38K9edtPzOwqmBbN5mlQqlOQUSkAqhO\noYTmLW1k+kMvsWb9Zvr26sbE0QM4eWhNucMqnqzXNWR9fEmgY5waSgoFmre0kUlzV7B5SzBbpXH9\nZibNXQGQjcSQ9bqGrI8vCXSMU0X3FAo0/aGXcgmhyeYt25j+0EtliqjIsl7XkPXxJYGOcaooKRRo\nzfrNkdpTJ+t1DVkfXxLoGKeKkkKB+vbqFqk9dbJe15D18SWBjnGqKCkUaOLoAXSr3rHQqVt1FRNH\nDyhTREWW9bqGrI8vCXSMU0U3mgvUdDM5s7OPsv4s/KyPLwl0jFNFdQoiIhUg3zoFXT4SybLls+Ha\ngXBFr+D78tnp6FvKRpePRLIqzvoA1R5kls4URLIqzvoA1R5klpKCSFbFWR+g2oPMUlIQyao46wNU\ne5BZSgoiWRVnfYBqDzJLSUEkq+JcO0PrcmSW6hRERCqA6hRERCQyJQUREclRUhARkRwlBRERyVFS\nEBGRHCUFERHJUVIQEZEcJQUREcmJLSmYWT8ze9zMXjCz583sG63sY2Z2vZm9YmbLzWxYXPFIAfTc\nfJGKEed6CluBb7n7EjPrASw2s0fc/YVm+xwPfDL8Ogy4MfwuSaHn5otUlNjOFNz9DXdfEv78LrAS\naLlw8UnAbzzwDNDLzPaKKybpBD03X6SilOSegpnVAUOBhS1eqgFWNdtezUcTB2Y2wcwazKxh7dq1\ncYUprdFz80UqSuxJwcy6A/8DfNPd3+lMH+4+w93r3b2+T58+xQ1Q2qfn5otUlFiTgplVEySEme4+\nt5VdGoF+zbZrwzZJCj03X6SixDn7yIBbgJXu/tM2drsX+GI4C+lwYIO7vxFXTNIJem6+SEWJc/bR\nSOALwAozWxa2fQ/oD+DuNwEPAGOAV4BNwJdjjEc6a/DpSgIiFSK2pODufwKsg30cuDCuGEREJBpV\nNIuISI6SgoiI5CgpiIhIjpKCiIjkKCmIiEiOkoKIiOQoKYiISI4FpQLpYWZrgdfLHUcb9gD+We4g\nYqTxpVeWxwYaXz72dvcOHx6XuqSQZGbW4O715Y4jLhpfemV5bKDxFZMuH4mISI6SgoiI5CgpFNeM\ncgcQM40vvbI8NtD4ikb3FEREJEdnCiIikqOk0AlmVmVmS83s/lZeG29ma81sWfj1f8oRYyHM7DUz\nWxHG39DK62Zm15vZK2a23MyGlSPOzshjbJ82sw3NPr9ULTFnZr3MbI6ZvWhmK81sRIvXU/vZQV7j\nS+3nZ2YDmsW9zMzeMbNvttgn9s8vzkV2suwbwEpg1zZev9vdv1bCeOJwtLu3NS/6eOCT4ddhwI3h\n97Rob2wAT7r72JJFU1w/A+a7+6lm9m/ALi1eT/tn19H4IKWfn7u/BAyB4A9PgqWJf9dit9g/P50p\nRGRmtcAJwM3ljqWMTgJ+44FngF5mtle5g6p0ZtYT+BTBMri4+7/cfX2L3VL72eU5vqwYBbzq7i0L\ndWP//JQUorsO+A7wYTv7nBKe2s0xs34liquYHHjYzBab2YRWXq8BVjXbXh22pUFHYwMYYWbPmtmD\nZnZQKYMr0D7AWuBX4eXNm83sYy32SfNnl8/4IL2fX3NnArNaaY/981NSiMDMxgJvuvvidna7D6hz\n98HAI8BtJQmuuI5w92EEp6oXmtmnyh1QEXU0tiUEjwM4GPg5MK/UARZgJ2AYcKO7DwXeAy4tb0hF\nlc/40vz5ARBeFjsR+G05/n0lhWhGAiea2WvAXcBnzOyO5ju4+zp3/yDcvBkYXtoQC+fujeH3Nwmu\naR7aYpdGoPkZUG3Ylngdjc25DtTlAAAD9UlEQVTd33H3jeHPDwDVZrZHyQPtnNXAandfGG7PIfgl\n2lxqPzvyGF/KP78mxwNL3P3/tfJa7J+fkkIE7j7J3WvdvY7g9O4xdz+n+T4tru+dSHBDOjXM7GNm\n1qPpZ+A/geda7HYv8MVwJsThwAZ3f6PEoUaWz9jM7BNmZuHPhxL8H1lX6lg7w93/F1hlZgPCplHA\nCy12S+VnB/mNL82fXzNn0fqlIyjB56fZR0VgZlOBBne/F7jIzE4EtgJvAePLGVsnfBz4Xfj/aifg\nTnefb2bnA7j7TcADwBjgFWAT8OUyxRpVPmM7FbjAzLYCm4EzPV0Vnl8HZoaXIP4GfDkjn12TjsaX\n6s8v/GPlWOCrzdpK+vmpollERHJ0+UhERHKUFEREJEdJQUREcpQUREQkR0lBRERylBREIgqfxNna\nE3JbbS/Cv3eymR3YbHuBmWV2PWIpLyUFkeQ7GTiww71EikBJQTInrFz+ffhQtOfM7IywfbiZ/TF8\nGN5DTdXn4V/ePwufYf9cWAmLmR1qZk+HD197qlklbb4x3Gpmi8L3nxS2jzezuWY238xeNrMfNXvP\neWb21/A9vzSzG8zsPwgq46eH8e0X7n5auN9fzezIIh06EVU0SyYdB6xx9xMgeOSymVUTPCDtJHdf\nGyaKHwDnhu/Zxd2HhA/IuxUYCLwIHOnuW83sGOCHwCl5xnAZwWNQzjWzXsAiM/tD+NoQYCjwAfCS\nmf0c2Ab8F8GzfN4FHgOedfenzOxe4H53nxOOB2Andz/UzMYAU4BjOnOgRFpSUpAsWgH8xMyuIfhl\n+qSZDST4Rf9I+Eu1Cmj+zJhZAO7+hJntGv4i7wHcZmafJHjkdnWEGP6T4OGJ3w63uwL9w58fdfcN\nAGb2ArA3sAfwR3d/K2z/LfDv7fQ/N/y+GKiLEJdIu5QUJHPc/a8WLFM4BrjKzB4leCLq8+4+oq23\ntbL9feBxd/+cmdUBCyKEYcAp4Wpa2xvNDiM4Q2iyjc79P2zqo7PvF2mV7ilI5phZX2CTu98BTCe4\nJPMS0MfCNX3NrNp2XICl6b7DEQRPntwA9GT7Y4nHRwzjIeDrzZ7YObSD/f8CHGVmu5nZTux4mepd\ngrMWkdgpKUgWDSK4hr+M4Hr7Ve7+L4InaF5jZs8Cy4D/aPae981sKXATcF7Y9iNgWtge9a/x7xNc\nblpuZs+H220K13n4IbAI+DPwGrAhfPkuYGJ4w3q/1nsQKQ49JVUqnpktAL7t7g1ljqO7u28MzxR+\nB9zq7i0XbheJlc4URJLjivDs5jng76RwKUlJP50piIhIjs4UREQkR0lBRERylBRERCRHSUFERHKU\nFEREJEdJQUREcv4/1UkqDOqyj6oAAAAASUVORK5CYII=\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pRlHhneRzW8r",
        "colab_type": "text"
      },
      "source": [
        "#### seems like everything is ok~~~"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MyTcfa78f9Zf",
        "colab_type": "text"
      },
      "source": [
        "## scikitlearn"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "t1YSreNEf9Zf",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from sklearn.neighbors import KNeighborsClassifier"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "C7pT4EVsf9Zi",
        "colab_type": "code",
        "outputId": "9ddec378-61a7-4dd8-fb73-d4c7c07ac9cd",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 70
        }
      },
      "source": [
        "clf_sk = KNeighborsClassifier()\n",
        "clf_sk.fit(X_train, y_train)"
      ],
      "execution_count": 73,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',\n",
              "                     metric_params=None, n_jobs=None, n_neighbors=5, p=2,\n",
              "                     weights='uniform')"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 73
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "N17NEbSqf9Zl",
        "colab_type": "code",
        "outputId": "8a5b6a23-29c2-4d15-de0c-d4f4b8869e7d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "clf_sk.score(X_test, y_test)"
      ],
      "execution_count": 74,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1.0"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 74
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9y79xayBf9Zq",
        "colab_type": "text"
      },
      "source": [
        "## kd树"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "k_fSjR7pOr1t",
        "colab_type": "text"
      },
      "source": [
        "### 构建kd树"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "69mplm2Tf9Zq",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# 算法3.2 平衡kd树\n",
        "\n",
        "class KdTree:\n",
        "    \"\"\"\n",
        "    build kdtree recursively along axis, split on median point.\n",
        "    k:      k dimensions\n",
        "    method: alternate/variance, 坐标轴轮替或最大方差轴\n",
        "    \"\"\"\n",
        "    \n",
        "    def __init__(self, k=2, method='alternate'):\n",
        "        self.k = k\n",
        "        self.method = method\n",
        "        \n",
        "    def build(self, points, depth=0):\n",
        "        n = len(points)\n",
        "        if n <= 0:\n",
        "            return None\n",
        "        \n",
        "        if self.method == 'alternate':\n",
        "            axis = depth % self.k\n",
        "        elif self.method == 'variance':\n",
        "            axis = np.argmax(np.var(points, axis=0), axis=0)\n",
        "        \n",
        "        sorted_points = sorted(points, key=lambda point: point[axis])\n",
        "        \n",
        "        return {\n",
        "            'point': sorted_points[n // 2],\n",
        "            'left': self.build(sorted_points[:n//2], depth+1),\n",
        "            'right': self.build(sorted_points[n//2+1:], depth+1)\n",
        "        }"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BOPlfGTKf9Zu",
        "colab_type": "text"
      },
      "source": [
        "#### 例3.2"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3W0H8H5Pf9Zu",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "data = np.array([[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]])\n",
        "\n",
        "kd1 = KdTree(k=2, method='alternate')\n",
        "tree1 = kd1.build(data)\n",
        "\n",
        "kd2 = KdTree(k=2, method='variance')\n",
        "tree2 = kd2.build(data)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HVMOPjgqDdsG",
        "colab_type": "code",
        "outputId": "223bb9f6-55bb-4f3e-9822-74e9cd32a48c",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 141
        }
      },
      "source": [
        "# friendly print\n",
        "\n",
        "pp = pprint.PrettyPrinter(indent=4)\n",
        "pp.pprint(tree1) # equal to figure. 3.4 《统计学习方法》"
      ],
      "execution_count": 77,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "{   'left': {   'left': {'left': None, 'point': array([2, 3]), 'right': None},\n",
            "                'point': array([5, 4]),\n",
            "                'right': {'left': None, 'point': array([4, 7]), 'right': None}},\n",
            "    'point': array([7, 2]),\n",
            "    'right': {   'left': {'left': None, 'point': array([8, 1]), 'right': None},\n",
            "                 'point': array([9, 6]),\n",
            "                 'right': None}}\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cdynMHq9KlYW",
        "colab_type": "code",
        "outputId": "30304630-ee40-4d60-d7dd-1edbf601ba8b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 141
        }
      },
      "source": [
        "pp.pprint(tree2) # 在该数据集上两种方法结果一样"
      ],
      "execution_count": 78,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "{   'left': {   'left': {'left': None, 'point': array([2, 3]), 'right': None},\n",
            "                'point': array([5, 4]),\n",
            "                'right': {'left': None, 'point': array([4, 7]), 'right': None}},\n",
            "    'point': array([7, 2]),\n",
            "    'right': {   'left': {'left': None, 'point': array([8, 1]), 'right': None},\n",
            "                 'point': array([9, 6]),\n",
            "                 'right': None}}\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3YfbHsHPO1Es",
        "colab_type": "text"
      },
      "source": [
        "### 查找kd树"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZT7MwyTlUaVJ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class SearchKdTree:\n",
        "    \"\"\"\n",
        "    search closest point\n",
        "    \"\"\"\n",
        "    def __init__(self, k=2):\n",
        "        self.k = k\n",
        "        \n",
        "    def __closer_distance(self, pivot, p1, p2):\n",
        "        if p1 is None:\n",
        "            return p2\n",
        "        if p2 is None:\n",
        "            return p1\n",
        "        \n",
        "        d1 = distance(pivot, p1)\n",
        "        d2 = distance(pivot, p2)\n",
        "\n",
        "        if d1 < d2:\n",
        "            return p1\n",
        "        else:\n",
        "            return p2\n",
        "    \n",
        "    def fit(self, root, point, depth=0):\n",
        "        if root is None:\n",
        "            return None\n",
        "        \n",
        "        axis = depth % self.k\n",
        "        \n",
        "        next_branch = None\n",
        "        opposite_branch = None\n",
        "        \n",
        "        if point[axis] < root['point'][axis]:\n",
        "            next_branch = root['left']\n",
        "            opposite_branch = root['right']\n",
        "        else:\n",
        "            next_branch = root['right']\n",
        "            opposite_branch = root['left']\n",
        "            \n",
        "        best = self.__closer_distance(point,\n",
        "                                     self.fit(next_branch,\n",
        "                                             point,\n",
        "                                             depth+1),\n",
        "                                     root['point'])\n",
        "        \n",
        "        if distance(point, best) > abs(point[axis] - root['point'][axis]):\n",
        "            best = self.__closer_distance(point,\n",
        "                                     self.fit(opposite_branch,\n",
        "                                             point,\n",
        "                                             depth+1),\n",
        "                                     best)\n",
        "            \n",
        "        return best"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fPVguOtoLEk5",
        "colab_type": "code",
        "outputId": "14a62f49-ad7d-4ec5-c484-97f0c39aca34",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# test\n",
        "point = [3.,4.5]\n",
        "\n",
        "search = SearchKdTree()\n",
        "best = search.fit(tree1, point, depth=0)\n",
        "print(best)"
      ],
      "execution_count": 80,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[2 3]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YXW7Q5kzbCrn",
        "colab_type": "code",
        "outputId": "d0244098-3648-406b-bdc7-3f31361ee817",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# force computing\n",
        "def force(points, point):\n",
        "    dis = np.power(np.sum(np.power(np.abs((points - point)), 2), 1), 1/2)\n",
        "    idx = np.argmin(dis, axis=0)\n",
        "    return points[idx]\n",
        "print(force(data, point))"
      ],
      "execution_count": 81,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[2 3]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cLP3E9ftLoku",
        "colab_type": "text"
      },
      "source": [
        "### test time cost between force and kd-tree"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wR827KmIf9Z1",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from time import time"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OywsDPeFf9Z3",
        "colab_type": "code",
        "outputId": "9b07cb74-c89d-4642-cd18-eb838510c868",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# generate sample points\n",
        "N = 500000\n",
        "K = 5\n",
        "points = np.random.randint(15, size=(N, K))\n",
        "print('points shape:{}'.format(points.shape))"
      ],
      "execution_count": 83,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "points shape:(500000, 5)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "g775x9ATUjig",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# build tree\n",
        "kd_tree = KdTree(k=K, method='alternate')\n",
        "tree = kd_tree.build(points)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yTjzO2HWcDzB",
        "colab_type": "code",
        "outputId": "e2e8aedc-341f-4b30-d11a-cd1b80458db3",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# generate test point\n",
        "#test_point = np.random.randint(10, size=(K))\n",
        "test_point = [14., 3.5, 10.6, 7.2, 9.2]\n",
        "print('test point: {}'.format(test_point))"
      ],
      "execution_count": 85,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "test point: [14.0, 3.5, 10.6, 7.2, 9.2]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Z_gLx8zHU7WH",
        "colab_type": "code",
        "outputId": "b1d91f94-6614-4334-accf-45b1fbba189b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "#search point\n",
        "\n",
        "start = time()\n",
        "seah = SearchKdTree()\n",
        "best = seah.fit(tree, test_point, depth=0)\n",
        "end = time()\n",
        "dist = distance(test_point, best)\n",
        "print('best point:{}, distance:{}, time cost:{}'.format(best, dist, end - start))"
      ],
      "execution_count": 86,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "best point:[14  3 11  7  9], distance:0.7000000000000001, time cost:5.568157196044922\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NAazqgu8TsRV",
        "colab_type": "code",
        "outputId": "5146b98c-d8fa-46c3-9e8a-d8a745ae210a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "# force computing\n",
        "\n",
        "start = time()\n",
        "best = force(points, test_point)\n",
        "end = time()\n",
        "dist = distance(test_point, best)\n",
        "print('best point:{}, distance:{}, time cost:{}'.format(best, dist, end - start))"
      ],
      "execution_count": 87,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "best point:[14  4 11  7  9], distance:0.7000000000000001, time cost:0.09840011596679688\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sKa7RDNdcbwy",
        "colab_type": "text"
      },
      "source": [
        "##### 看上去，相比于在大量的数据点中寻找与目标最近的点，kd树不需要一个个查找,O(n)的复杂的，看上去确实效率提高了。但是！对于numpy来说，numpy的矩阵运算是常量时间复杂度O(1)，效率极高。在内存许可的情况下，可以快速查找出符合要求的点, 速度比kd树还快, 从上面的时间消耗可以看出。"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RgNCo_qdJWwn",
        "colab_type": "text"
      },
      "source": [
        "#### assignment"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vXxbAwtiBsgJ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "### 作业\n",
        "\n",
        "data = np.array([[5,4], [9,6],[4,7],[2,3],[8,1],[7,2]])\n",
        "label = np.array([0,0,0,1,1,1])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZqYz0AnrCiEf",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 123
        },
        "outputId": "64578427-2709-418d-e5dd-78f08b49c093"
      },
      "source": [
        "data"
      ],
      "execution_count": 89,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[5, 4],\n",
              "       [9, 6],\n",
              "       [4, 7],\n",
              "       [2, 3],\n",
              "       [8, 1],\n",
              "       [7, 2]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 89
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "M8oRJQCpLQeG",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "bcb6467e-f0c4-4f74-e4ff-7909f7fe09b1"
      },
      "source": [
        "label"
      ],
      "execution_count": 102,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([0, 0, 0, 1, 1, 1])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 102
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aHxqk1ZqEQsY",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "252f7e15-3a29-49ce-8f3a-28eb6eef6efb"
      },
      "source": [
        "k = KNN(data, label)\n",
        "k.predict([5,3])"
      ],
      "execution_count": 90,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(0, array([[5, 4]]), array([1.]))"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 90
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "m978zEFyKjUP",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        },
        "outputId": "ebd3133a-e455-4238-9554-91378aa647d4"
      },
      "source": [
        "distance(data,[5,3])"
      ],
      "execution_count": 101,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([1.        , 5.        , 4.12310563, 3.        , 3.60555128,\n",
              "       2.23606798])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 101
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eJkmbszxJnnd",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "5f3129db-07db-4e15-b028-8ab2042d9990"
      },
      "source": [
        "# sklearn\n",
        "\n",
        "clf_sk1 = KNeighborsClassifier(n_neighbors=1)\n",
        "clf_sk1.fit(data, label)\n",
        "\n",
        "clf_sk1.predict(np.array([5,3]).reshape(-1, 2))"
      ],
      "execution_count": 106,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([0])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 106
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FrtByLpAMBAr",
        "colab_type": "text"
      },
      "source": [
        "## Reference\n",
        "* 李航 《统计学习方法》  \n",
        "* https://github.com/fengdu78/lihang-code/blob/master/code/%E7%AC%AC3%E7%AB%A0%20k%E8%BF%91%E9%82%BB%E6%B3%95(KNearestNeighbors)/KNN.ipynb  \n",
        "* https://www.youtube.com/watch?v=u4M5rRYwRHs&t=449s  \n",
        "* https://www.youtube.com/watch?v=XqXSGSKc8NU&t=335s  \n",
        "* https://www.youtube.com/watch?v=DlPrTGbO19E  "
      ]
    }
  ]
}